package stack;

import java.util.Stack;

public class Solution {

    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            if(!stack.isEmpty() && stack.peek() == s.charAt(i)){
                stack.pop();
            }else{
                stack.add(s.charAt(i));
            }

        }
        StringBuffer ret = new StringBuffer();
        while(!stack.isEmpty()){
            ret.append(stack.pop());
        }
        return ret.reverse().toString();
    }

    public String removeDuplicates2(String s) {
        StringBuffer ret = new StringBuffer();
        char[] tmp = s.toCharArray();

        for(int i = 0; i < s.length(); i++){
            if(ret.length() > 0 && tmp[i] == ret.charAt(ret.length() - 1)){
                ret.deleteCharAt(ret.length() - 1);
            }else{
                ret.append(tmp[i]);
            }
        }
        return ret.toString();
    }


    public boolean backspaceCompare(String s, String t) {
        StringBuffer s1 = new StringBuffer();
        StringBuffer s2 = new StringBuffer();
        char[] ch1 = s.toCharArray();
        char[] ch2 = t.toCharArray();

        for(char ch : ch1){
            if(ch == '#'){
                if(s1.length() > 0) { s1.deleteCharAt(s1.length() - 1);}
            }else{
                s1.append(ch);
            }
        }

        for(char ch : ch2){
            if(ch == '#'){
                if(s2.length() > 0) { s2.deleteCharAt(s2.length() - 1);}
            }else{
                s2.append(ch);
            }
        }

        return (s1.toString()).equals(s2.toString());
    }

    public boolean backspaceCompare2(String s, String t) {
        return (change(s)).equals(change(t));
    }
    public String change(String s){
        StringBuffer ret = new StringBuffer();
        char[] ch1 = s.toCharArray();

        for(char ch: ch1){
            if(ch == '#'){
                if(ret.length() > 0) { ret.deleteCharAt(ret.length() - 1);}
            }else{
                ret.append(ch);
            }
        }
        return ret.toString();
    }


    public int calculate(String s) {
        Stack<Integer> ret = new Stack<>();
        char[] ch = s.toCharArray();
        char op = '+';

        for(int i = 0; i < ch.length; ){
            if(ch[i] == ' '){
                i++;
            }else if(ch[i] >= '0' && ch[i] <= '9'){
                int tmp = 0;
                while(i < ch.length && ch[i] >= '0' && ch[i] <= '9'){
                    tmp = tmp * 10 + (ch[i] - '0');
                    i++;
                }

                if(op == '+'){
                    ret.push(tmp);
                }else if(op == '-'){
                    ret.push(-tmp);
                }else if(op == '*'){
                    ret.push(ret.pop() * tmp);
                }else{
                    ret.push(ret.pop() / tmp);
                }
            }else{
                op = ch[i];
                i++;
            }
        }

        int cur = 0;
        while(!ret.isEmpty()){
            cur += ret.pop();
        }
        return cur;
    }


    public String decodeString(String s) {
        char[] ch = s.toCharArray();

        Stack<StringBuffer> st = new Stack<>();
        st.push(new StringBuffer());
        Stack<Integer> num = new Stack<>();

        int i = 0, n = s.length();

        while(i < n){
            if(ch[i] >= '0' && ch[i] <= '9'){
                int tmp = 0;
                while(i < n && ch[i] >= '0' && ch[i] <= '9'){
                    tmp = tmp * 10 + (ch[i] - '0');
                    i++;
                }
                num.push(tmp);
            }else if(ch[i] == '['){
                i++;
                StringBuffer tmp = new StringBuffer();
                while(i < n && ch[i] >= 'a' && ch[i] <= 'z'){
                    tmp.append(ch[i]);
                    i++;
                }
                st.push(tmp);
            }else if(ch[i] == ']'){
                StringBuffer tmp = st.pop();
                int k = num.pop();
                while(k-- != 0){
                    st.peek().append(tmp);
                }
                i++;
            }else{
                StringBuffer tmp = new StringBuffer();
                while(i < n && ch[i] >= 'a' && ch[i] <= 'z'){
                    tmp.append(ch[i]);
                    i++;
                }
                st.peek().append(tmp);
            }
        }
        return st.peek().toString();
    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed.length != popped.length) { return false;}
        Stack<Integer> stack = new Stack<>();
        int i = 0, n = pushed.length;
        for(int x : pushed){
            stack.push(x);
            while(!stack.isEmpty() && stack.peek() == popped[i]){
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}
